﻿#pragma once
#include<iostream>
#include<assert.h>
#include<cstdbool>
#include<vector>
using namespace std;
namespace shuaiming
{
	enum Colour
	{
		RED,
		BLACK
	};
	// 这里就实现了泛型，T可推导key结构也可以推导key/value结构
	template<class T>
	struct RBTreeNode
	{
		T _data;
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		Colour _col;
		RBTreeNode(const T& data)
			:_data(data)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)
		{}
	};
	//             本身     引用        指针
	template<class T, class Ref, class Ptr>
	struct RBTreeIterator
	{
		typedef RBTreeNode<T> Node;
		typedef RBTreeIterator<T, Ref, Ptr> Self;

		RBTreeIterator(Node* node, Node* root)
			:_node(node)
			, _root(root)
		{}
		Node* _node;
		Node* _root;
		// 请完善迭代器的++操作，让迭代器可以移动
		// 其实按照搜索树的中序遍历来看，就是找比当前结点大一点(或相等)的那个
		Self& operator++()
		{
			// 右不为空则去找当前结点右子树的最左结点(当前结点右子树的最小结点)
			if (_node->_right)
			{
				Node* cur = _node->_right;
				while (cur->_left)
					cur = cur->_left;
				_node = cur;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				// 两个结束：
				// 1.cur一直找到了根，
				// 2.找到符合祖先中孩子是父亲左的关系的那个祖先(即cur==parent->_left)
				while (parent != _root->_parent && cur != parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}
		// 其实按照搜索树的中序遍历来看，就是找比当前结点小一点(或相等)的那个
		Self& operator--()
		{
			// --不同的是还有一种特殊情况就是--end(),也就是迭代器走到了end()去--操作
			if (_node == _root->_parent)// --end()
			{
				Node* cur = _root->_right;
				while (cur && cur->_right)
					cur = cur->_right;
				_node = cur;
			}
			// 左不为空则去找当前结点左子树的最右结点(当前结点左子树的最大结点)
			else if (_node->_left)
			{
				Node* cur = _node->_left;
				while (cur->_right)
					cur = cur->_right;
				_node = cur;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				// 两个结束：
				// 1.cur一直找到了根，
				// 2.找到符合祖先中孩子是父亲右的关系的那个祖先(即cur==parent->_right)
				while (parent != _root->_parent && cur != parent->_right)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}
		// 请完善下面两个操作，让迭代器可以像指针一样操作
		T& operator*() { return _node->_data; }
		T* operator->() { return &_node->_data; }

		// 请完善下面两个操作，让迭代器能够支持比较
		bool operator!=(const Self& s) const { return _node != s._node; }
		bool operator==(const Self& s) const { return _node == s._node; }
	};

	template<class K, class T, class KeyOfT>
	class RBTree
	{
		typedef RBTreeNode<T> Node;
	public:
		typedef typename RBTreeIterator<T, T&, T*> Iterator;
		typedef typename RBTreeIterator<T, const T&, const T*> Const_Iterator;


		Iterator Begin() { return Iterator(LeftMost(), GetRoot()); }
		Iterator End() { return  Iterator(_pHead, GetRoot()); }
		Const_Iterator Begin() const { return Const_Iterator(LeftMost(), GetRoot()); }
		Const_Iterator End() const { return Const_Iterator(_pHead, GetRoot()); } 
		~RBTree()
		{
			Destroy(GetRoot());
			GetRoot() = nullptr;
		}
		RBTree()// 增加哨兵位头结点
		{
			_pHead = new Node(T());
			_pHead->_left = _pHead;
			_pHead->_right = _pHead;
		}

		pair<Iterator, bool> Insert(const T& data)
		{
			if (GetRoot() == nullptr)// 空树---插入即为根
			{
				Node* root = new Node(data);
				root->_parent = _pHead;
				_pHead->_parent = root;
				_pHead->_left = _pHead->_right = root;
				root->_col = BLACK;
				return make_pair(Iterator({ GetRoot(),GetRoot() }), true);
			}
			KeyOfT kof;
			Node* cur = GetRoot();
			Node* parent = nullptr;
			while (cur)
			{
				if (kof(data) < kof(cur->_data))// 因为data可能是key，也可能是key/value
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (kof(data) > kof(cur->_data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return make_pair(Iterator({ cur,GetRoot() }), false);
			}
			cur = new Node(data);
			Node* newnode = cur;
			cur->_parent = parent;
			if (kof(data) < kof(parent->_data))
				parent->_left = cur;
			else
				parent->_right = cur;
			// 插入完成，开始维护红黑树的规则
			while (parent != _pHead && parent->_col != BLACK)// 到哨兵位或父亲为黑就可退出
			{
				Node* grandfather = parent->_parent;
				Node* uncle = grandfather->_left;// 假设法先假设
				if (uncle == parent)
					uncle = grandfather->_right;
				// 三种情况---都是主要看uncle
				// 1.只变色---适用于uncle存在且为红(无论cur插入在左还是右皆可如此)
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
				}
				// 旋转+变色---适用于uncle不存在(即cur必为新增) 或 uncle存在且为黑(即cur必不是新增)---要分单旋和双旋
				else if (uncle == nullptr || uncle && uncle->_col == BLACK)
				{
					// 2.单旋+变色
					// 右单旋
					if (grandfather->_left == parent && parent->_left == cur)// 纯粹左边高
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					// 左单旋
					else if (grandfather->_right == parent && parent->_right == cur)// 纯粹右边高
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					// 3.双旋+变色
					// 左右双旋
					else if (grandfather->_left == parent && parent->_right == cur)// 不纯粹右边高
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					// 右左双旋
					else if (grandfather->_right == parent && parent->_left == cur)// 不纯粹左边高
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					else
						assert(false);
					// 因为有哨兵位的原因，每插入一个结点就要去维护哨兵位结点指针的指向
					// 不能立即插入后就改变指向，因为插入后可能引发旋转，应在旋转后维护
					_pHead->_left = LeftMost();
					_pHead->_right = RightMost();
					break;
				}
				else
					assert(false);
				cur = grandfather;
				parent = cur->_parent;
			}
			// 颜色变化可能导致根变色，这里直接强制控制为黑色
			GetRoot()->_col = BLACK;
			return make_pair(Iterator({ newnode,GetRoot() }), true);
		}

		// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
		Node* Find(const T& data) const
		{
			if (GetRoot() == nullptr)
				return nullptr;
			Node* cur = GetRoot();
			while (cur)
			{
				if (kof(data) < kof(cur->_data))
					cur = cur->_left;
				else if (kof(data) > kof(cur->_data))
					cur = cur->_right;
				else
					return cur;
			}
			return nullptr;
		}
		// 获取红黑树最左侧节点
		Node* LeftMost() const
		{
			Node* root = GetRoot();
			if (nullptr == root)
				return _pHead;
			Node* cur = root;
			while (cur->_left)
				cur = cur->_left;
			return cur;
		}
		// 获取红黑树最右侧节点
		Node* RightMost() const 
		{
			Node* root = GetRoot();
			if (nullptr == root)
				return _pHead;
			Node* cur = root;
			while (cur->_right)
				cur = cur->_right;
			return cur;
		}
	private:
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
		// 左单旋
		void RotateL(Node* pParent)
		{
			Node* subR = pParent->_right;
			Node* subRL = subR->_left;
			Node* grandfather = pParent->_parent;
			pParent->_right = subRL;
			if (subRL)
				subRL->_parent = pParent;
			subR->_left = pParent;
			pParent->_parent = subR;
			if (pParent == GetRoot())
				GetRoot() = subR;
			else
			{
				if (grandfather->_left == pParent)
					grandfather->_left = subR;
				else
					grandfather->_right = subR;
			}
			subR->_parent = grandfather;
		}
		// 右单旋
		void RotateR(Node* pParent)
		{
			Node* subL = pParent->_left;
			Node* subLR = subL->_right;
			Node* grandfather = pParent->_parent;
			pParent->_left = subLR;
			if (subLR)
				subLR->_parent = pParent;
			subL->_right = pParent;
			pParent->_parent = subL;
			if (pParent == GetRoot())// 小心，如果是整个的根，则根结点要变化
				GetRoot() = subL;
			else// 局部根
			{
				if (grandfather->_left == pParent)
					grandfather->_left = subL;
				else
					grandfather->_right = subL;
			}
			subL->_parent = grandfather;
		}
		// 为了操作树简单起见：获取根节点
		Node*& GetRoot() const
		{
			return _pHead->_parent;// 没有数据则返回空，因为_pHead->_parent缺省值为nullptr
		}
	private:
		Node* _pHead;
	};
}